package com.LeeCode;

/**
 * 两个字符串的切换距离
 */

public class Code3361 {
    public static void main(String[] args) {
        String s = "abab", t = "baba";
        int[] nextCost = {100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int[] previousCost = {1, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        System.out.println(new Code3361().shiftDistance(s, t, nextCost, previousCost));
    }

    public long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        long[] preSumNext = new long[27], preSumPrev = new long[27];
        for (int i = 0; i < 26; i++) {
            preSumNext[i + 1] = preSumNext[i] + nextCost[i];
            preSumPrev[i + 1] = preSumPrev[i] + previousCost[i];
        }
        char[] sChar = s.toCharArray(), tChar = t.toCharArray();
        long totalCost = 0;
        for (int i = 0; i < sChar.length; i++) {
            char from = sChar[i];
            char to = tChar[i];

            if (from == to) {
                continue;
            }

            int fromIndex = from - 'a';
            int toIndex = to - 'a';

            // 计算向前切换的代价（使用前缀和优化）
            long forwardCost;
            if (fromIndex > toIndex) {
                // 直接向前：fromIndex -> toIndex
                forwardCost = preSumPrev[fromIndex + 1] - preSumPrev[toIndex + 1];
            } else {
                // 绕一圈：fromIndex -> 25 -> 0 -> toIndex
                forwardCost = preSumPrev[26] - preSumPrev[toIndex + 1] + preSumPrev[fromIndex + 1];
            }

            // 计算向后切换的代价（使用前缀和优化）
            long backwardCost;
            if (fromIndex < toIndex) {
                // 直接向后：fromIndex -> toIndex
                backwardCost = preSumNext[toIndex] - preSumNext[fromIndex];
            } else {
                // 绕一圈：fromIndex -> 0 -> 25 -> toIndex
                backwardCost = preSumNext[toIndex] + (preSumNext[26] - preSumNext[fromIndex]);
            }

            totalCost += Math.min(forwardCost, backwardCost);
        }

        return totalCost;
    }
}
